/*
 * contrib/pg_trgm/trgm_op.c
 */
#include "postgres.h"

#include <ctype.h>

#include "catalog/pg_type.h"
#include "lib/qunique.h"
#include "trgm.h"
#include "tsearch/ts_locale.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"
#include "utils/pg_crc.h"

PG_MODULE_MAGIC;

/* GUC 变量 */
double		similarity_threshold = 0.3f;
double		word_similarity_threshold = 0.6f;
double		strict_word_similarity_threshold = 0.5f;

void		_PG_init(void);

PG_FUNCTION_INFO_V1(set_limit);
PG_FUNCTION_INFO_V1(show_limit);
PG_FUNCTION_INFO_V1(show_trgm);
PG_FUNCTION_INFO_V1(similarity);
PG_FUNCTION_INFO_V1(word_similarity);
PG_FUNCTION_INFO_V1(strict_word_similarity);
PG_FUNCTION_INFO_V1(similarity_dist);
PG_FUNCTION_INFO_V1(similarity_op);
PG_FUNCTION_INFO_V1(word_similarity_op);
PG_FUNCTION_INFO_V1(word_similarity_commutator_op);
PG_FUNCTION_INFO_V1(word_similarity_dist_op);
PG_FUNCTION_INFO_V1(word_similarity_dist_commutator_op);
PG_FUNCTION_INFO_V1(strict_word_similarity_op);
PG_FUNCTION_INFO_V1(strict_word_similarity_commutator_op);
PG_FUNCTION_INFO_V1(strict_word_similarity_dist_op);
PG_FUNCTION_INFO_V1(strict_word_similarity_dist_commutator_op);

/* 带位置的三元组 */
typedef struct
{
	trgm		trg;
	int			index;
} pos_trgm;

/* 三元组边界类型 */
typedef uint8 TrgmBound;
#define TRGM_BOUND_LEFT				0x01	/* 三元组是单词的左边界 */
#define TRGM_BOUND_RIGHT			0x02	/* 三元组是单词的右边界 */

/* 单词相似性标志 */
#define WORD_SIMILARITY_CHECK_ONLY	0x01	/* 仅检查文本中相似搜索模式的存在 */
#define WORD_SIMILARITY_STRICT		0x02	/* 强制边界的扩展与单词边界匹配 */

/*
 * 模块加载回调
 */
void _PG_init(void)
{
	/* 定义自定义 GUC 变量。 */
	DefineCustomRealVariable("pg_trgm.similarity_threshold",
							 "Sets the threshold used by the % operator.",
							 "Valid range is 0.0 .. 1.0.",
							 &similarity_threshold,
							 0.3,
							 0.0,
							 1.0,
							 PGC_USERSET,
							 0,
							 NULL,
							 NULL,
							 NULL);
	DefineCustomRealVariable("pg_trgm.word_similarity_threshold",
							 "Sets the threshold used by the <% operator.",
							 "Valid range is 0.0 .. 1.0.",
							 &word_similarity_threshold,
							 0.6,
							 0.0,
							 1.0,
							 PGC_USERSET,
							 0,
							 NULL,
							 NULL,
							 NULL);
	DefineCustomRealVariable("pg_trgm.strict_word_similarity_threshold",
							 "Sets the threshold used by the <<% operator.",
							 "Valid range is 0.0 .. 1.0.",
							 &strict_word_similarity_threshold,
							 0.5,
							 0.0,
							 1.0,
							 PGC_USERSET,
							 0,
							 NULL,
							 NULL,
							 NULL);

	MarkGUCPrefixReserved("pg_trgm");
}

/*
 * 已弃用函数。
 * 使用“pg_trgm.similarity_threshold” GUC 变量替代此函数。
 */
Datum set_limit(PG_FUNCTION_ARGS)
{
	float4		fc_nlimit = PG_GETARG_FLOAT4(0);
	char	   *fc_nlimit_str;
	Oid			fc_func_out_oid;
	bool		fc_is_varlena;

	getTypeOutputInfo(FLOAT4OID, &fc_func_out_oid, &fc_is_varlena);

	fc_nlimit_str = OidOutputFunctionCall(fc_func_out_oid, Float4GetDatum(fc_nlimit));

	SetConfigOption("pg_trgm.similarity_threshold", fc_nlimit_str,
					PGC_USERSET, PGC_S_SESSION);

	PG_RETURN_FLOAT4(similarity_threshold);
}


/*
 * 获取给定索引扫描策略编号的相似性阈值。
 */
double index_strategy_get_limit(StrategyNumber fc_strategy)
{
	switch (fc_strategy)
	{
		case SimilarityStrategyNumber:
			return similarity_threshold;
		case WordSimilarityStrategyNumber:
			return word_similarity_threshold;
		case StrictWordSimilarityStrategyNumber:
			return strict_word_similarity_threshold;
		default:
			elog(ERROR, "unrecognized strategy number: %d", fc_strategy);
			break;
	}

	return 0.0;					/* 保持编译器安静 */
}

/*
 * 已弃用函数。
 * 使用“pg_trgm.similarity_threshold” GUC 变量替代此函数。
 */
Datum show_limit(PG_FUNCTION_ARGS)
{
	PG_RETURN_FLOAT4(similarity_threshold);
}

static int fc_comp_trgm(const void *fc_a, const void *fc_b)
{
	return CMPTRGM(fc_a, fc_b);
}

/*
 * 找到字符串中的第一个单词，返回指向单词的指针，
 * endword 指向单词后面的字符
 */
static char * fc_find_word(char *fc_str, int fc_lenstr, char **fc_endword, int *fc_charlen)
{
	char	   *fc_beginword = fc_str;

	while (fc_beginword - fc_str < fc_lenstr && !ISWORDCHR(fc_beginword))
		fc_beginword += pg_mblen(fc_beginword);

	if (fc_beginword - fc_str >= fc_lenstr)
		return NULL;

	*fc_endword = fc_beginword;
	*fc_charlen = 0;
	while (*fc_endword - fc_str < fc_lenstr && ISWORDCHR(*fc_endword))
	{
		*fc_endword += pg_mblen(*fc_endword);
		(*fc_charlen)++;
	}

	return fc_beginword;
}

/*
 * 将一个三元组（可能包含多个字节的三个字符）简化为一个 trgm，
 * 它总是正好三个字节。如果我们有三个单字节字符，
 * 我们就按原样使用它们；否则我们生成一个哈希值。
 */
void compact_trigram(trgm *fc_tptr, char *fc_str, int fc_bytelen)
{
	if (fc_bytelen == 3)
	{
		CPTRGM(fc_tptr, fc_str);
	}
	else
	{
		pg_crc32	fc_crc;

		INIT_LEGACY_CRC32(fc_crc);
		COMP_LEGACY_CRC32(fc_crc, fc_str, fc_bytelen);
		FIN_LEGACY_CRC32(fc_crc);

		/*
		 * 仅使用 crc 的 3 个高字节，希望这足够好
		 */
		CPTRGM(fc_tptr, &fc_crc);
	}
}

/*
 * 从单词中添加三元组（已填充）。
 */
static trgm *
fc_make_trigrams(trgm *fc_tptr, char *fc_str, int fc_bytelen, int fc_charlen)
{
	char	   *fc_ptr = fc_str;

	if (fc_charlen < 3)
		return fc_tptr;

	if (fc_bytelen > fc_charlen)
	{
		/* 查找多字节字符边界并应用 compact_trigram */
		int			fc_lenfirst = pg_mblen(fc_str),
					fc_lenmiddle = pg_mblen(fc_str + fc_lenfirst),
					fc_lenlast = pg_mblen(fc_str + fc_lenfirst + fc_lenmiddle);

		while ((fc_ptr - fc_str) + fc_lenfirst + fc_lenmiddle + fc_lenlast <= fc_bytelen)
		{
			compact_trigram(fc_tptr, fc_ptr, fc_lenfirst + fc_lenmiddle + fc_lenlast);

			fc_ptr += fc_lenfirst;
			fc_tptr++;

			fc_lenfirst = fc_lenmiddle;
			fc_lenmiddle = fc_lenlast;
			fc_lenlast = pg_mblen(fc_ptr + fc_lenfirst + fc_lenmiddle);
		}
	}
	else
	{
		/* 当没有多字节字符时的快速路径 */
		Assert(fc_bytelen == fc_charlen);

		while (fc_ptr - fc_str < fc_bytelen - 2 /* 三元组数量 = strlen - 2 */ )
		{
			CPTRGM(fc_tptr, fc_ptr);
			fc_ptr++;
			fc_tptr++;
		}
	}

	return fc_tptr;
}

/*
 * 创建不排序且不删除重复项的三元组数组。
 *
 * trg: 返回三元组数组的地方。
 * str: 源字符串，长度为 slen 字节。
 * bounds: 返回三元组边界的位置（如有需要）。
 *
 * 返回生成数组的长度。
 */
static int fc_generate_trgm_only(trgm *fc_trg, char *fc_str, int fc_slen, TrgmBound *fc_bounds)
{
	trgm	   *fc_tptr;
	char	   *fc_buf;
	int			fc_charlen,
				fc_bytelen;
	char	   *fc_bword,
			   *fc_eword;

	if (fc_slen + LPADDING + RPADDING < 3 || fc_slen == 0)
		return 0;

	fc_tptr = fc_trg;

	/* 为大小写折叠、空格填充的单词分配缓冲区 */
	fc_buf = (char *) palloc(fc_slen * pg_database_encoding_max_length() + 4);

	if (LPADDING > 0)
	{
		*fc_buf = ' ';
		if (LPADDING > 1)
			*(fc_buf + 1) = ' ';
	}

	fc_eword = fc_str;
	while ((fc_bword = fc_find_word(fc_eword, fc_slen - (fc_eword - fc_str), &fc_eword, &fc_charlen)) != NULL)
	{
#ifdef IGNORECASE
		fc_bword = lowerstr_with_len(fc_bword, fc_eword - fc_bword);
		fc_bytelen = strlen(fc_bword);
#else
		fc_bytelen = fc_eword - fc_bword;
#endif

		memcpy(fc_buf + LPADDING, fc_bword, fc_bytelen);

#ifdef IGNORECASE
		pfree(fc_bword);
#endif

		fc_buf[LPADDING + fc_bytelen] = ' ';
		fc_buf[LPADDING + fc_bytelen + 1] = ' ';

		/* 计算三元组并标记它们的边界（如有需要） */
		if (fc_bounds)
			fc_bounds[fc_tptr - fc_trg] |= TRGM_BOUND_LEFT;
		fc_tptr = fc_make_trigrams(fc_tptr, fc_buf, fc_bytelen + LPADDING + RPADDING,
							 fc_charlen + LPADDING + RPADDING);
		if (fc_bounds)
			fc_bounds[fc_tptr - fc_trg - 1] |= TRGM_BOUND_RIGHT;
	}

	pfree(fc_buf);

	return fc_tptr - fc_trg;
}

/*
 * 防止下面的 palloc 请求可能的溢出。(我们
 * 不担心附加常数，因为 palloc 可以检测
 * 较大于 MaxAllocSize 的请求 --- 我们只需要
 * 防止乘法中的整数溢出。)
 */
static void fc_protect_out_of_mem(int fc_slen)
{
	if ((Size) (fc_slen / 2) >= (MaxAllocSize / (sizeof(trgm) * 3)) ||
		(Size) fc_slen >= (MaxAllocSize / pg_database_encoding_max_length()))
		ereport(ERROR,
				(errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
				 errmsg("out of memory")));
}

/*
 * 创建带排序和删除重复项的三元组数组。
 *
 * str: 源字符串，长度为 slen 字节。
 *
 * 返回排序后的唯一三元组数组。
 */
TRGM * generate_trgm(char *fc_str, int fc_slen)
{
	TRGM	   *fc_trg;
	int			fc_len;

	fc_protect_out_of_mem(fc_slen);

	fc_trg = (TRGM *) palloc(TRGMHDRSIZE + sizeof(trgm) * (fc_slen / 2 + 1) * 3);
	fc_trg->flag = ARRKEY;

	fc_len = fc_generate_trgm_only(GETARR(fc_trg), fc_str, fc_slen, NULL);
	SET_VARSIZE(fc_trg, CALCGTSIZE(ARRKEY, fc_len));

	if (fc_len == 0)
		return fc_trg;

	/*
	 * 使三元组唯一。
	 */
	if (fc_len > 1)
	{
		qsort((void *) GETARR(fc_trg), fc_len, sizeof(trgm), fc_comp_trgm);
		fc_len = qunique(GETARR(fc_trg), fc_len, sizeof(trgm), fc_comp_trgm);
	}

	SET_VARSIZE(fc_trg, CALCGTSIZE(ARRKEY, fc_len));

	return fc_trg;
}

/*
 * 从两个三元组数组 trg1 和 trg2 创建位置三元组数组。
 *
 * trg1: 搜索模式的三元组数组，长度为 len1。trg1 是所需的
 *		 单词，其位置无关，替换为 -1。
 * trg2: 文本的三元组数组，长度为 len2。trg2 是我们
 *		 查找的稻草堆，并需要存储其位置。
 *
 * 返回连接的三元组数组。
 */
static pos_trgm *
fc_make_positional_trgm(trgm *fc_trg1, int fc_len1, trgm *fc_trg2, int fc_len2)
{
	pos_trgm   *fc_result;
	int			fc_i,
				fc_len = fc_len1 + fc_len2;

	fc_result = (pos_trgm *) palloc(sizeof(pos_trgm) * fc_len);

	for (fc_i = 0; fc_i < fc_len1; fc_i++)
	{
		memcpy(&fc_result[fc_i].trg, &fc_trg1[fc_i], sizeof(trgm));
		fc_result[fc_i].index = -1;
	}

	for (fc_i = 0; fc_i < fc_len2; fc_i++)
	{
		memcpy(&fc_result[fc_i + fc_len1].trg, &fc_trg2[fc_i], sizeof(trgm));
		fc_result[fc_i + fc_len1].index = fc_i;
	}

	return fc_result;
}

/*
 * 比较位置三元组：首先比较三元组，其次比较位置。
 */
static int fc_comp_ptrgm(const void *fc_v1, const void *fc_v2)
{
	const pos_trgm *fc_p1 = (const pos_trgm *) fc_v1;
	const pos_trgm *fc_p2 = (const pos_trgm *) fc_v2;
	int			fc_cmp;

	fc_cmp = CMPTRGM(fc_p1->trg, fc_p2->trg);
	if (fc_cmp != 0)
		return fc_cmp;

	if (fc_p1->index < fc_p2->index)
		return -1;
	else if (fc_p1->index == fc_p2->index)
		return 0;
	else
		return 1;
}

/*
 * 迭代搜索函数，用于计算与字符串中单词的最大相似度。只有在check_only == false时才计算最大相似度。
 *
 * trg2indexes: 存储数组"found"索引的数组。
 * found: 存储真或假的值数组。
 * ulen1: 数组"trg1"的唯一三元组计数。
 * len2: 数组"trg2"和数组"trg2indexes"的长度。
 * len: 数组"found"的长度。
 * lags: 一组布尔标志，用于参数化相似度计算。
 * bounds: 每个三元组是否是单词的左/右边界。
 *
 * 返回单词相似度。
 */
static float4 fc_iterate_word_similarity(int *fc_trg2indexes,
						bool *fc_found,
						int fc_ulen1,
						int fc_len2,
						int fc_len,
						uint8 fc_flags,
						TrgmBound *fc_bounds)
{
	int		   *fc_lastpos,
				fc_i,
				fc_ulen2 = 0,
				fc_count = 0,
				fc_upper = -1,
				fc_lower;
	float4		fc_smlr_cur,
				fc_smlr_max = 0.0f;
	double		fc_threshold;

	Assert(fc_bounds || !(fc_flags & WORD_SIMILARITY_STRICT));

	/* 选择合适的阈值 */
	fc_threshold = (fc_flags & WORD_SIMILARITY_STRICT) ?
		strict_word_similarity_threshold :
		word_similarity_threshold;

	/*
	 * 将第一个三元组视为严格单词相似度的初始下边界，或稍后用存在的第一个三元组初始化平常单词相似度。
	 */
	fc_lower = (fc_flags & WORD_SIMILARITY_STRICT) ? 0 : -1;

	/* 记住每个三元组的最后位置 */
	fc_lastpos = (int *) palloc(sizeof(int) * fc_len);
	memset(fc_lastpos, -1, sizeof(int) * fc_len);

	for (fc_i = 0; fc_i < fc_len2; fc_i++)
	{
		/* 获取下一个三元组的索引 */
		int			fc_trgindex = fc_trg2indexes[fc_i];

		/* 更新该三元组的最后位置 */
		if (fc_lower >= 0 || fc_found[fc_trgindex])
		{
			if (fc_lastpos[fc_trgindex] < 0)
			{
				fc_ulen2++;
				if (fc_found[fc_trgindex])
					fc_count++;
			}
			fc_lastpos[fc_trgindex] = fc_i;
		}

		/*
		 * 如果三元组是严格单词相似度的上边界，或者三元组存在于所需子字符串中，则调整上边界，以便计算平常单词相似度。
		 */
		if ((fc_flags & WORD_SIMILARITY_STRICT) ? (fc_bounds[fc_i] & TRGM_BOUND_RIGHT)
			: fc_found[fc_trgindex])
		{
			int			fc_prev_lower,
						fc_tmp_ulen2,
						fc_tmp_lower,
						fc_tmp_count;

			fc_upper = fc_i;
			if (fc_lower == -1)
			{
				fc_lower = fc_i;
				fc_ulen2 = 1;
			}

			fc_smlr_cur = CALCSML(fc_count, fc_ulen1, fc_ulen2);

			/* 也试着调整下边界以获得更大的相似度 */
			fc_tmp_count = fc_count;
			fc_tmp_ulen2 = fc_ulen2;
			fc_prev_lower = fc_lower;
			for (fc_tmp_lower = fc_lower; fc_tmp_lower <= fc_upper; fc_tmp_lower++)
			{
				float		fc_smlr_tmp;
				int			fc_tmp_trgindex;

				/*
				 * 仅在三元组是严格单词相似度的下边界时调整下边界，或者将每个三元组视为平常单词相似度的下边界。
				 */
				if (!(fc_flags & WORD_SIMILARITY_STRICT)
					|| (fc_bounds[fc_tmp_lower] & TRGM_BOUND_LEFT))
				{
					fc_smlr_tmp = CALCSML(fc_tmp_count, fc_ulen1, fc_tmp_ulen2);
					if (fc_smlr_tmp > fc_smlr_cur)
					{
						fc_smlr_cur = fc_smlr_tmp;
						fc_ulen2 = fc_tmp_ulen2;
						fc_lower = fc_tmp_lower;
						fc_count = fc_tmp_count;
					}

					/*
					 * 如果我们只检查单词相似度是否大于阈值，则无需计算最大相似度。
					 */
					if ((fc_flags & WORD_SIMILARITY_CHECK_ONLY)
						&& fc_smlr_cur >= fc_threshold)
						break;
				}

				fc_tmp_trgindex = fc_trg2indexes[fc_tmp_lower];
				if (fc_lastpos[fc_tmp_trgindex] == fc_tmp_lower)
				{
					fc_tmp_ulen2--;
					if (fc_found[fc_tmp_trgindex])
						fc_tmp_count--;
				}
			}

			fc_smlr_max = Max(fc_smlr_max, fc_smlr_cur);

			/*
			 * 如果我们只检查单词相似度是否大于阈值，则无需计算最大相似度。
			 */
			if ((fc_flags & WORD_SIMILARITY_CHECK_ONLY) && fc_smlr_max >= fc_threshold)
				break;

			for (fc_tmp_lower = fc_prev_lower; fc_tmp_lower < fc_lower; fc_tmp_lower++)
			{
				int			fc_tmp_trgindex;

				fc_tmp_trgindex = fc_trg2indexes[fc_tmp_lower];
				if (fc_lastpos[fc_tmp_trgindex] == fc_tmp_lower)
					fc_lastpos[fc_tmp_trgindex] = -1;
			}
		}
	}

	pfree(fc_lastpos);

	return fc_smlr_max;
}

/*
 * 计算单词相似度。
 * 此函数准备两个数组："trg2indexes"和"found"。然后，这些数组用于通过iterate_word_similarity()函数计算单词相似度。
 *
 * "trg2indexes"是存储数组"found"索引的数组。
 * 换句话说：
 * trg2indexes[j] = i;
 * found[i] = true（或false）;
 * 如果found[i] == true，则数组"trg1"中存在三元组trg2[j]。
 * 如果found[i] == false，则数组"trg1"中不存在三元组trg2[j]。
 *
 * str1: 查找模式字符串，长度为slen1字节。
 * str2: 我们要在其中寻找单词的文本，长度为slen2字节。
 * flags: 一组布尔标志，用于参数化相似度计算。
 *
 * 返回单词相似度。
 */
static float4 fc_calc_word_similarity(char *fc_str1, int fc_slen1, char *fc_str2, int fc_slen2,
					 uint8 fc_flags)
{
	bool	   *fc_found;
	pos_trgm   *fc_ptrg;
	trgm	   *fc_trg1;
	trgm	   *fc_trg2;
	int			fc_len1,
				fc_len2,
				fc_len,
				fc_i,
				fc_j,
				fc_ulen1;
	int		   *fc_trg2indexes;
	float4		fc_result;
	TrgmBound  *fc_bounds;

	fc_protect_out_of_mem(fc_slen1 + fc_slen2);

	/* 制作位置三元组 */
	fc_trg1 = (trgm *) palloc(sizeof(trgm) * (fc_slen1 / 2 + 1) * 3);
	fc_trg2 = (trgm *) palloc(sizeof(trgm) * (fc_slen2 / 2 + 1) * 3);
	if (fc_flags & WORD_SIMILARITY_STRICT)
		fc_bounds = (TrgmBound *) palloc0(sizeof(TrgmBound) * (fc_slen2 / 2 + 1) * 3);
	else
		fc_bounds = NULL;

	fc_len1 = fc_generate_trgm_only(fc_trg1, fc_str1, fc_slen1, NULL);
	fc_len2 = fc_generate_trgm_only(fc_trg2, fc_str2, fc_slen2, fc_bounds);

	fc_ptrg = fc_make_positional_trgm(fc_trg1, fc_len1, fc_trg2, fc_len2);
	fc_len = fc_len1 + fc_len2;
	qsort(fc_ptrg, fc_len, sizeof(pos_trgm), fc_comp_ptrgm);

	pfree(fc_trg1);
	pfree(fc_trg2);

	/*
	 * 合并位置三元组数组：枚举每个三元组并查找其在所需单词中的存在。
	 */
	fc_trg2indexes = (int *) palloc(sizeof(int) * fc_len2);
	fc_found = (bool *) palloc0(sizeof(bool) * fc_len);

	fc_ulen1 = 0;
	fc_j = 0;
	for (fc_i = 0; fc_i < fc_len; fc_i++)
	{
		if (fc_i > 0)
		{
			int			fc_cmp = CMPTRGM(fc_ptrg[fc_i - 1].trg, fc_ptrg[fc_i].trg);

			if (fc_cmp != 0)
			{
				if (fc_found[fc_j])
					fc_ulen1++;
				fc_j++;
			}
		}

		if (fc_ptrg[fc_i].index >= 0)
		{
			fc_trg2indexes[fc_ptrg[fc_i].index] = fc_j;
		}
		else
		{
			fc_found[fc_j] = true;
		}
	}
	if (fc_found[fc_j])
		fc_ulen1++;

	/* 运行迭代过程以找到与单词的最大相似度 */
	fc_result = fc_iterate_word_similarity(fc_trg2indexes, fc_found, fc_ulen1, fc_len2, fc_len,
									 fc_flags, fc_bounds);

	pfree(fc_trg2indexes);
	pfree(fc_found);
	pfree(fc_ptrg);

	return fc_result;
}


/*
 * 提取搜索字符串中下一个非通配符部分，即由'_'或'%'元字符、非单词字符或字符串结束界定的单词。
 *
 * str: 源字符串，长度为lenstr字节（不必以null结束）
 * buf: 返回子字符串的位置（必须足够长）
 * *bytelen: 接收找到的子字符串的字节长度
 * *charlen: 接收找到的子字符串的字符长度
 *
 * 返回指向源字符串中找到的子字符串结束+1的指针。
 * 如果未找到单词，则返回NULL（在这种情况下buf、bytelen、charlen未设置）
 *
 * 如果找到的单词被非单词字符或字符串边界界定，那么此函数将包括相应的填充空格到buf中。
 */
static const char * fc_get_wildcard_part(const char *fc_str, int fc_lenstr,
				  char *fc_buf, int *fc_bytelen, int *fc_charlen)
{
	const char *fc_beginword = fc_str;
	const char *fc_endword;
	char	   *fc_s = fc_buf;
	bool		fc_in_leading_wildcard_meta = false;
	bool		fc_in_trailing_wildcard_meta = false;
	bool		fc_in_escape = false;
	int			fc_clen;

	/*
	 * 查找第一个单词字符，记住前一个字符是否是通配符元字符。注意，在这个循环到下一个循环中in_escape状态持续存在，
	 * 因为我们可能在一个in_escape的单词字符处退出。
	 */
	while (fc_beginword - fc_str < fc_lenstr)
	{
		if (fc_in_escape)
		{
			if (ISWORDCHR(fc_beginword))
				break;
			fc_in_escape = false;
			fc_in_leading_wildcard_meta = false;
		}
		else
		{
			if (ISESCAPECHAR(fc_beginword))
				fc_in_escape = true;
			else if (ISWILDCARDCHAR(fc_beginword))
				fc_in_leading_wildcard_meta = true;
			else if (ISWORDCHR(fc_beginword))
				break;
			else
				fc_in_leading_wildcard_meta = false;
		}
		fc_beginword += pg_mblen(fc_beginword);
	}

	/*
	 * 处理字符串结束。
	 */
	if (fc_beginword - fc_str >= fc_lenstr)
		return NULL;

	/*
	 * 如果前一个字符不是通配符元字符，则添加左侧填充空格。
	 */
	*fc_charlen = 0;
	if (!fc_in_leading_wildcard_meta)
	{
		if (LPADDING > 0)
		{
			*fc_s++ = ' ';
			(*fc_charlen)++;
			if (LPADDING > 1)
			{
				*fc_s++ = ' ';
				(*fc_charlen)++;
			}
		}
	}

	/*
	 * 在复制到buf中直到通配符元字符、非单词字符或字符串边界。复制期间删除转义。
	 */
	fc_endword = fc_beginword;
	while (fc_endword - fc_str < fc_lenstr)
	{
		fc_clen = pg_mblen(fc_endword);
		if (fc_in_escape)
		{
			if (ISWORDCHR(fc_endword))
			{
				memcpy(fc_s, fc_endword, fc_clen);
				(*fc_charlen)++;
				fc_s += fc_clen;
			}
			else
			{
				/*
				 * 在遇到转义字符时，将endword备份到转义字符，这样后续的get_wildcard_part将从转义字符处重新开始。
				 * 我们在这里假设转义字符是单字节的。
				 */
				fc_endword--;
				break;
			}
			fc_in_escape = false;
		}
		else
		{
			if (ISESCAPECHAR(fc_endword))
				fc_in_escape = true;
			else if (ISWILDCARDCHAR(fc_endword))
			{
				fc_in_trailing_wildcard_meta = true;
				break;
			}
			else if (ISWORDCHR(fc_endword))
			{
				memcpy(fc_s, fc_endword, fc_clen);
				(*fc_charlen)++;
				fc_s += fc_clen;
			}
			else
				break;
		}
		fc_endword += fc_clen;
	}

	/*
	 * 如果下一个字符不是通配符元字符，则添加右侧填充空格。
	 */
	if (!fc_in_trailing_wildcard_meta)
	{
		if (RPADDING > 0)
		{
			*fc_s++ = ' ';
			(*fc_charlen)++;
			if (RPADDING > 1)
			{
				*fc_s++ = ' ';
				(*fc_charlen)++;
			}
		}
	}

	*fc_bytelen = fc_s - fc_buf;
	return fc_endword;
}

/*
 * 为通配符搜索字符串生成三元组。
 *
 * 返回的三元组数组必须出现在匹配通配符字符串的任何字符串中。
 * 例如，给定模式"a%bcd%"将提取出三元组" a"和"bcd"。
 */
TRGM * generate_wildcard_trgm(const char *fc_str, int fc_slen)
{
	TRGM	   *fc_trg;
	char	   *fc_buf,
			   *fc_buf2;
	trgm	   *fc_tptr;
	int			fc_len,
				fc_charlen,
				fc_bytelen;
	const char *fc_eword;

	fc_protect_out_of_mem(fc_slen);

	fc_trg = (TRGM *) palloc(TRGMHDRSIZE + sizeof(trgm) * (fc_slen / 2 + 1) * 3);
	fc_trg->flag = ARRKEY;
	SET_VARSIZE(fc_trg, TRGMHDRSIZE);

	if (fc_slen + LPADDING + RPADDING < 3 || fc_slen == 0)
		return fc_trg;

	fc_tptr = GETARR(fc_trg);

	/* 为空白填充但尚未区分大小写的单词分配缓冲区 */
	fc_buf = palloc(sizeof(char) * (fc_slen + 4));

	/*
	 * 从每个由get_wildcard_part提取的子字符串中提取三元组。
	 */
	fc_eword = fc_str;
	while ((fc_eword = fc_get_wildcard_part(fc_eword, fc_slen - (fc_eword - fc_str),
									  fc_buf, &fc_bytelen, &fc_charlen)) != NULL)
	{
#ifdef IGNORECASE
		fc_buf2 = lowerstr_with_len(fc_buf, fc_bytelen);
		fc_bytelen = strlen(fc_buf2);
#else
		fc_buf2 = fc_buf;
#endif

		/*
		 * 计算三元组
		 */
		fc_tptr = fc_make_trigrams(fc_tptr, fc_buf2, fc_bytelen, fc_charlen);

#ifdef IGNORECASE
		pfree(fc_buf2);
#endif
	}

	pfree(fc_buf);

	if ((fc_len = fc_tptr - GETARR(fc_trg)) == 0)
		return fc_trg;

	/*
	 * 使三元组唯一。
	 */
	if (fc_len > 1)
	{
		qsort((void *) GETARR(fc_trg), fc_len, sizeof(trgm), fc_comp_trgm);
		fc_len = qunique(GETARR(fc_trg), fc_len, sizeof(trgm), fc_comp_trgm);
	}

	SET_VARSIZE(fc_trg, CALCGTSIZE(ARRKEY, fc_len));

	return fc_trg;
}

uint32 trgm2int(trgm *fc_ptr)
{
	uint32		fc_val = 0;

	fc_val |= *(((unsigned char *) fc_ptr));
	fc_val <<= 8;
	fc_val |= *(((unsigned char *) fc_ptr) + 1);
	fc_val <<= 8;
	fc_val |= *(((unsigned char *) fc_ptr) + 2);

	return fc_val;
}

Datum show_trgm(PG_FUNCTION_ARGS)
{
	text	   *fc_in = PG_GETARG_TEXT_PP(0);
	TRGM	   *fc_trg;
	Datum	   *fc_d;
	ArrayType  *fc_a;
	trgm	   *fc_ptr;
	int			fc_i;

	fc_trg = generate_trgm(VARDATA_ANY(fc_in), VARSIZE_ANY_EXHDR(fc_in));
	fc_d = (Datum *) palloc(sizeof(Datum) * (1 + ARRNELEM(fc_trg)));

	for (fc_i = 0, fc_ptr = GETARR(fc_trg); fc_i < ARRNELEM(fc_trg); fc_i++, fc_ptr++)
	{
		text	   *fc_item = (text *) palloc(VARHDRSZ + Max(12, pg_database_encoding_max_length() * 3));

		if (pg_database_encoding_max_length() > 1 && !ISPRINTABLETRGM(fc_ptr))
		{
			snprintf(VARDATA(fc_item), 12, "0x%06x", trgm2int(fc_ptr));
			SET_VARSIZE(fc_item, VARHDRSZ + strlen(VARDATA(fc_item)));
		}
		else
		{
			SET_VARSIZE(fc_item, VARHDRSZ + 3);
			CPTRGM(VARDATA(fc_item), fc_ptr);
		}
		fc_d[fc_i] = PointerGetDatum(fc_item);
	}

	fc_a = construct_array(fc_d,
						ARRNELEM(fc_trg),
						TEXTOID,
						-1,
						false,
						TYPALIGN_INT);

	for (fc_i = 0; fc_i < ARRNELEM(fc_trg); fc_i++)
		pfree(DatumGetPointer(fc_d[fc_i]));

	pfree(fc_d);
	pfree(fc_trg);
	PG_FREE_IF_COPY(fc_in, 0);

	PG_RETURN_POINTER(fc_a);
}

float4
cnt_sml(TRGM *fc_trg1, TRGM *fc_trg2, bool fc_inexact)
{
	trgm	   *fc_ptr1,
			   *fc_ptr2;
	int			fc_count = 0;
	int			fc_len1,
				fc_len2;

	fc_ptr1 = GETARR(fc_trg1);
	fc_ptr2 = GETARR(fc_trg2);

	fc_len1 = ARRNELEM(fc_trg1);
	fc_len2 = ARRNELEM(fc_trg2);

	/* 需要显式测试以避免在两个长度都为0时进行0/0除法 */
	if (fc_len1 <= 0 || fc_len2 <= 0)
		return (float4) 0.0;

	while (fc_ptr1 - GETARR(fc_trg1) < fc_len1 && fc_ptr2 - GETARR(fc_trg2) < fc_len2)
	{
		int			fc_res = CMPTRGM(fc_ptr1, fc_ptr2);

		if (fc_res < 0)
			fc_ptr1++;
		else if (fc_res > 0)
			fc_ptr2++;
		else
		{
			fc_ptr1++;
			fc_ptr2++;
			fc_count++;
		}
	}

	/*
	 * 如果是非精确的，则len2等于count，因为我们不知道非精确搜索中第二个字符串的实际长度，
	 * 我们可以假设count是len2的下限。
	 */
	return CALCSML(fc_count, fc_len1, fc_inexact ? fc_count : fc_len2);
}


/*
 * 返回trg2是否包含trg1中的所有三元组。
 * 这依赖于三元组数组的排序。
 */
bool trgm_contained_by(TRGM *fc_trg1, TRGM *fc_trg2)
{
	trgm	   *fc_ptr1,
			   *fc_ptr2;
	int			fc_len1,
				fc_len2;

	fc_ptr1 = GETARR(fc_trg1);
	fc_ptr2 = GETARR(fc_trg2);

	fc_len1 = ARRNELEM(fc_trg1);
	fc_len2 = ARRNELEM(fc_trg2);

	while (fc_ptr1 - GETARR(fc_trg1) < fc_len1 && fc_ptr2 - GETARR(fc_trg2) < fc_len2)
	{
		int			fc_res = CMPTRGM(fc_ptr1, fc_ptr2);

		if (fc_res < 0)
			return false;
		else if (fc_res > 0)
			fc_ptr2++;
		else
		{
			fc_ptr1++;
			fc_ptr2++;
		}
	}
	if (fc_ptr1 - GETARR(fc_trg1) < fc_len1)
		return false;
	else
		return true;
}

/*
 * 返回一个palloc'd布尔数组，显示“query”中的每个三元组是否存在于三元组数组“key”中。
 * 这依赖于“key”数组的排序，但“query”不必是。
 */
bool *
trgm_presence_map(TRGM *fc_query, TRGM *fc_key)
{
	bool	   *fc_result;
	trgm	   *fc_ptrq = GETARR(fc_query),
			   *fc_ptrk = GETARR(fc_key);
	int			fc_lenq = ARRNELEM(fc_query),
				fc_lenk = ARRNELEM(fc_key),
				fc_i;

	fc_result = (bool *) palloc0(fc_lenq * sizeof(bool));

	/* 对每个查询三元组在key数组中进行二分搜索 */
	for (fc_i = 0; fc_i < fc_lenq; fc_i++)
	{
		int			fc_lo = 0;
		int			fc_hi = fc_lenk;

		while (fc_lo < fc_hi)
		{
			int			fc_mid = (fc_lo + fc_hi) / 2;
			int			fc_res = CMPTRGM(fc_ptrq, fc_ptrk + fc_mid);

			if (fc_res < 0)
				fc_hi = fc_mid;
			else if (fc_res > 0)
				fc_lo = fc_mid + 1;
			else
			{
				fc_result[fc_i] = true;
				break;
			}
		}
		fc_ptrq++;
	}

	return fc_result;
}

Datum similarity(PG_FUNCTION_ARGS)
{
	text	   *fc_in1 = PG_GETARG_TEXT_PP(0);
	text	   *fc_in2 = PG_GETARG_TEXT_PP(1);
	TRGM	   *fc_trg1,
			   *fc_trg2;
	float4		fc_res;

	fc_trg1 = generate_trgm(VARDATA_ANY(fc_in1), VARSIZE_ANY_EXHDR(fc_in1));
	fc_trg2 = generate_trgm(VARDATA_ANY(fc_in2), VARSIZE_ANY_EXHDR(fc_in2));

	fc_res = cnt_sml(fc_trg1, fc_trg2, false);

	pfree(fc_trg1);
	pfree(fc_trg2);
	PG_FREE_IF_COPY(fc_in1, 0);
	PG_FREE_IF_COPY(fc_in2, 1);

	PG_RETURN_FLOAT4(fc_res);
}

Datum word_similarity(PG_FUNCTION_ARGS)
{
	text	   *fc_in1 = PG_GETARG_TEXT_PP(0);
	text	   *fc_in2 = PG_GETARG_TEXT_PP(1);
	float4		fc_res;

	fc_res = fc_calc_word_similarity(VARDATA_ANY(fc_in1), VARSIZE_ANY_EXHDR(fc_in1),
							   VARDATA_ANY(fc_in2), VARSIZE_ANY_EXHDR(fc_in2),
							   0);

	PG_FREE_IF_COPY(fc_in1, 0);
	PG_FREE_IF_COPY(fc_in2, 1);
	PG_RETURN_FLOAT4(fc_res);
}

Datum strict_word_similarity(PG_FUNCTION_ARGS)
{
	text	   *fc_in1 = PG_GETARG_TEXT_PP(0);
	text	   *fc_in2 = PG_GETARG_TEXT_PP(1);
	float4		fc_res;

	fc_res = fc_calc_word_similarity(VARDATA_ANY(fc_in1), VARSIZE_ANY_EXHDR(fc_in1),
							   VARDATA_ANY(fc_in2), VARSIZE_ANY_EXHDR(fc_in2),
							   WORD_SIMILARITY_STRICT);

	PG_FREE_IF_COPY(fc_in1, 0);
	PG_FREE_IF_COPY(fc_in2, 1);
	PG_RETURN_FLOAT4(fc_res);
}

Datum similarity_dist(PG_FUNCTION_ARGS)
{
	float4		fc_res = DatumGetFloat4(DirectFunctionCall2(similarity,
														 PG_GETARG_DATUM(0),
														 PG_GETARG_DATUM(1)));

	PG_RETURN_FLOAT4(1.0 - fc_res);
}

Datum similarity_op(PG_FUNCTION_ARGS)
{
	float4		fc_res = DatumGetFloat4(DirectFunctionCall2(similarity,
														 PG_GETARG_DATUM(0),
														 PG_GETARG_DATUM(1)));

	PG_RETURN_BOOL(fc_res >= similarity_threshold);
}

Datum word_similarity_op(PG_FUNCTION_ARGS)
{
	text	   *fc_in1 = PG_GETARG_TEXT_PP(0);
	text	   *fc_in2 = PG_GETARG_TEXT_PP(1);
	float4		fc_res;

	fc_res = fc_calc_word_similarity(VARDATA_ANY(fc_in1), VARSIZE_ANY_EXHDR(fc_in1),
							   VARDATA_ANY(fc_in2), VARSIZE_ANY_EXHDR(fc_in2),
							   WORD_SIMILARITY_CHECK_ONLY);

	PG_FREE_IF_COPY(fc_in1, 0);
	PG_FREE_IF_COPY(fc_in2, 1);
	PG_RETURN_BOOL(fc_res >= word_similarity_threshold);
}

Datum word_similarity_commutator_op(PG_FUNCTION_ARGS)
{
	text	   *fc_in1 = PG_GETARG_TEXT_PP(0);
	text	   *fc_in2 = PG_GETARG_TEXT_PP(1);
	float4		fc_res;

	fc_res = fc_calc_word_similarity(VARDATA_ANY(fc_in2), VARSIZE_ANY_EXHDR(fc_in2),
							   VARDATA_ANY(fc_in1), VARSIZE_ANY_EXHDR(fc_in1),
							   WORD_SIMILARITY_CHECK_ONLY);

	PG_FREE_IF_COPY(fc_in1, 0);
	PG_FREE_IF_COPY(fc_in2, 1);
	PG_RETURN_BOOL(fc_res >= word_similarity_threshold);
}

Datum word_similarity_dist_op(PG_FUNCTION_ARGS)
{
	text	   *fc_in1 = PG_GETARG_TEXT_PP(0);
	text	   *fc_in2 = PG_GETARG_TEXT_PP(1);
	float4		fc_res;

	fc_res = fc_calc_word_similarity(VARDATA_ANY(fc_in1), VARSIZE_ANY_EXHDR(fc_in1),
							   VARDATA_ANY(fc_in2), VARSIZE_ANY_EXHDR(fc_in2),
							   0);

	PG_FREE_IF_COPY(fc_in1, 0);
	PG_FREE_IF_COPY(fc_in2, 1);
	PG_RETURN_FLOAT4(1.0 - fc_res);
}

Datum word_similarity_dist_commutator_op(PG_FUNCTION_ARGS)
{
	text	   *fc_in1 = PG_GETARG_TEXT_PP(0);
	text	   *fc_in2 = PG_GETARG_TEXT_PP(1);
	float4		fc_res;

	fc_res = fc_calc_word_similarity(VARDATA_ANY(fc_in2), VARSIZE_ANY_EXHDR(fc_in2),
							   VARDATA_ANY(fc_in1), VARSIZE_ANY_EXHDR(fc_in1),
							   0);

	PG_FREE_IF_COPY(fc_in1, 0);
	PG_FREE_IF_COPY(fc_in2, 1);
	PG_RETURN_FLOAT4(1.0 - fc_res);
}

Datum strict_word_similarity_op(PG_FUNCTION_ARGS)
{
	text	   *fc_in1 = PG_GETARG_TEXT_PP(0);
	text	   *fc_in2 = PG_GETARG_TEXT_PP(1);
	float4		fc_res;

	fc_res = fc_calc_word_similarity(VARDATA_ANY(fc_in1), VARSIZE_ANY_EXHDR(fc_in1),
							   VARDATA_ANY(fc_in2), VARSIZE_ANY_EXHDR(fc_in2),
							   WORD_SIMILARITY_CHECK_ONLY | WORD_SIMILARITY_STRICT);

	PG_FREE_IF_COPY(fc_in1, 0);
	PG_FREE_IF_COPY(fc_in2, 1);
	PG_RETURN_BOOL(fc_res >= strict_word_similarity_threshold);
}

Datum strict_word_similarity_commutator_op(PG_FUNCTION_ARGS)
{
	text	   *fc_in1 = PG_GETARG_TEXT_PP(0);
	text	   *fc_in2 = PG_GETARG_TEXT_PP(1);
	float4		fc_res;

	fc_res = fc_calc_word_similarity(VARDATA_ANY(fc_in2), VARSIZE_ANY_EXHDR(fc_in2),
							   VARDATA_ANY(fc_in1), VARSIZE_ANY_EXHDR(fc_in1),
							   WORD_SIMILARITY_CHECK_ONLY | WORD_SIMILARITY_STRICT);

	PG_FREE_IF_COPY(fc_in1, 0);
	PG_FREE_IF_COPY(fc_in2, 1);
	PG_RETURN_BOOL(fc_res >= strict_word_similarity_threshold);
}

Datum strict_word_similarity_dist_op(PG_FUNCTION_ARGS)
{
	text	   *fc_in1 = PG_GETARG_TEXT_PP(0);
	text	   *fc_in2 = PG_GETARG_TEXT_PP(1);
	float4		fc_res;

	fc_res = fc_calc_word_similarity(VARDATA_ANY(fc_in1), VARSIZE_ANY_EXHDR(fc_in1),
							   VARDATA_ANY(fc_in2), VARSIZE_ANY_EXHDR(fc_in2),
							   WORD_SIMILARITY_STRICT);

	PG_FREE_IF_COPY(fc_in1, 0);
	PG_FREE_IF_COPY(fc_in2, 1);
	PG_RETURN_FLOAT4(1.0 - fc_res);
}

Datum strict_word_similarity_dist_commutator_op(PG_FUNCTION_ARGS)
{
	text	   *fc_in1 = PG_GETARG_TEXT_PP(0);
	text	   *fc_in2 = PG_GETARG_TEXT_PP(1);
	float4		fc_res;

	fc_res = fc_calc_word_similarity(VARDATA_ANY(fc_in2), VARSIZE_ANY_EXHDR(fc_in2),
							   VARDATA_ANY(fc_in1), VARSIZE_ANY_EXHDR(fc_in1),
							   WORD_SIMILARITY_STRICT);

	PG_FREE_IF_COPY(fc_in1, 0);
	PG_FREE_IF_COPY(fc_in2, 1);
	PG_RETURN_FLOAT4(1.0 - fc_res);
}
